Instructions:¶
Read section 8.6 of your text and contemplate problem 10 (it's a pain, so you don't have to go through it all, just think about what the process would entail). You can do it for extra credit.
Take or find an image, and using the tools in this Python notebook, find the rank k approximation of the matrix of your image for a few different values of k. I will look through the code below for your work.
Assume that the amount of memory taken by a matrix is the number of entries of the matrix. When the computer saves the original image, it saves the whole original image matrix $A$, but when it saves the SVD it saves the matrices $U$ and $V$ and the list of singular values along the diagonal of $\Sigma$. Compare the size of your original image file, the size of the full singular value decomposition, and the size of the approximations you found in part 2. How much space did you save? Find a value of k that’s a good balance between file size and image quality. Enter your answer to this question in the indicated cell below.
The rank k approximation uses the first k columns of the matrix $U$, the first k rows of the matrix $V$, and the first k singular values along the diagonal of the matrix $\Sigma$. Try approximating by taking a different set of rows and columns, for example, skipping the first 3 columns of $U$, rows of $V$, and diagonal values of $\Sigma$. How much worse does the image quality get? This gives you an idea of the relative importance of the few largest eigenvectors in representing your image. Include your experimentation in the this notebook so I can see the various different sets you used and the resulting image quality.
Your work for questions 1 and 2 should appear below¶
Answer for part 1¶
from google.colab import files
uploaded1 = files.upload()
uploaded2 = files.upload()
uploaded3 = files.upload()
uploadedfinale = files.upload()
Saving S.V.Dpt1.jpg to S.V.Dpt1 (3).jpg
Saving S.V.Dpt2.jpg to S.V.Dpt2 (2).jpg
Saving S.V.Dpt3patched.jpg to S.V.Dpt3patched.jpg
Saving S.V.Dfinale.jpg to S.V.Dfinale (2).jpg
from PIL import Image
part1 = Image.open("S.V.Dpt1.jpg").rotate(-90, expand=True)
part1 = part1.resize((600, 800))
display(part1)
part2 = Image.open("S.V.Dpt2.jpg").rotate(-90, expand=True)
part2 = part2.resize((600, 800))
display(part2)
part3 = Image.open("S.V.Dpt3patched.jpg").rotate(-90, expand=True)
part3 = part3.resize((600, 800))
display(part3)
finale = Image.open("S.V.Dfinale.jpg")
finale = finale.resize((1000, 350))
display(finale)
from PIL import Image
import numpy as np
import matplotlib.pyplot as plt
import math
from google.colab import files
uploaded = files.upload()
Saving dog.jpg to dog.jpg
dog=Image.open("dog.jpg")
display(dog)
dog=dog.convert('L') #convert to black and white
dog=dog.resize((600,400)) #resize to 600x400 pixels
display(dog)
dogarray=np.asarray(dog)
dogarray
array([[ 54, 54, 53, ..., 81, 81, 82],
[ 54, 54, 54, ..., 81, 82, 81],
[ 52, 53, 54, ..., 80, 81, 81],
...,
[134, 134, 132, ..., 83, 85, 87],
[132, 134, 132, ..., 86, 85, 85],
[131, 130, 131, ..., 88, 86, 86]], dtype=uint8)
(u,s,v)=np.linalg.svd(dogarray)
Sigma = np.zeros((600, 400))
Sigma[0:400, 0:400] = np.diag(s)
# Rank 100 approximation of the matrix
approxdogarray = u[0:400, 0:100] @ Sigma[0:100, 0:100] @ v[0:100, 0:600]
approxdogarray=approxdogarray.astype(np.uint8)
approxdog=Image.fromarray(approxdogarray)
approxdog
Answer for part 2¶
from google.colab import files
uploaded = files.upload()
Saving MATH352SVD.jpg to MATH352SVD.jpg
from PIL import Image
import numpy as np
#before
print("Original Image")
# Open and preprocess the image
image = Image.open("MATH352SVD.jpg")
link = Image.open("MATH352SVD.jpg")
display(link)
image = image.convert('L') # convert to black and white
image = image.resize((600, 400)) # resize to 600x400 pixels
# Display the original image in black and white
print("Image scaled and monochromed")
display(image)
#spacer
print("")
# Convert the image to a numpy array
image_array = np.asarray(image)
print(f"Image array = \n{image_array} ")
#spacer
print("")
# Perform Singular Value Decomposition
u, s, v = np.linalg.svd(image_array)
# Construct the diagonal matrix Sigma
Sigma = np.zeros((600, 400))
Sigma[0:400, 0:400] = np.diag(s)
# Rank k approximation of the matrix
def rank_k_approximation(k):
approx_image_array = u[:, :k] @ Sigma[:k, :k] @ v[:k, :]
approx_image_array = approx_image_array.astype(np.uint8)
return Image.fromarray(approx_image_array)
# Calculate memory sizes
original_memory = image_array.size # Number of entries in the original array
svd_memory = u.size + Sigma.size + v.size # Number of entries in U, Sigma, and V matrices
approx_memory = {}
# Calculate memory sizes for each approximation and display the approximated images
for k in [10, 50, 100, 200]:
# Calculate memory size for the current approximation
approx_memory[k] = (u[:, :k].size + Sigma[:k, :k].size + v[:k, :].size)
# Display the memory size above the current approximation
print(f"Memory size for rank {k} approximation:", approx_memory[k])
# Display the current approximation
display(rank_k_approximation(k))
# Print memory sizes and the value of k that balances image quality and space saving
print("\nOriginal image memory:", original_memory)
print("SVD memory:", svd_memory)
print("Size of storage needed for rank k SVD approximation:")
for k, memory in approx_memory.items():
print(f"Rank {k} approximation memory:", memory)
Original Image
Image scaled and monochromed
Image array = [[ 65 65 65 ... 68 67 67] [ 65 65 65 ... 67 67 67] [ 64 64 64 ... 67 67 67] ... [101 101 102 ... 80 80 80] [101 101 101 ... 79 79 79] [101 101 101 ... 80 79 79]] Memory size for rank 10 approximation: 10100
Memory size for rank 50 approximation: 52500
Memory size for rank 100 approximation: 110000
Memory size for rank 200 approximation: 240000
Original image memory: 240000 SVD memory: 760000 Size of storage needed for rank k SVD approximation: Rank 10 approximation memory: 10100 Rank 50 approximation memory: 52500 Rank 100 approximation memory: 110000 Rank 200 approximation memory: 240000
Enter your answer to question 3 in this cell¶
Size of your original file: 240000
Size of storage of full SVD: 760000
Value of k you found that seemed a good balance of image quality and space saving: k = 100
Size of storage needed for your rank k SVD approximation: 110000
Add your code for question 4 in the cells below¶
# Rank k approximation of the matrix with different subsets
def rank_k_approximation_experiments(k):
# Skip the first 3 columns of U, rows of V, and diagonal values of Sigma
approx_image_array = u[:, 3:k+3] @ Sigma[3:k+3, 3:k+3] @ v[3:k+3, :]
approx_image_array = approx_image_array.astype(np.uint8)
return Image.fromarray(approx_image_array)
# Experimenting with different sets of rows and columns, we'll use the same k values for consistency
for k in [10, 50, 100, 200]:
# Display the current approximation
print(f"rank {k} aprroximation")
display(rank_k_approximation_experiments(k))
#Holy crap nightmare fuel
rank 10 aprroximation
rank 50 aprroximation
rank 100 aprroximation
rank 200 aprroximation
yeahhhhh it looks way worse when you lose that data. The finer background details are completely obliterated and a lot of the facial details also get lost. You can see that the silloette is still somewhat recognizable, but this really shows how important those first 3 rows and columns of data are.